package sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    private static final int[] array = {2, 8, 7, 1, 3, 5, 6, 4};

    public static void main(String[] args) {
//        随机化算法
        int i = new Random(47).nextInt(array.length);
        int temp = array[array.length - 1];
        array[array.length - 1] = array[i];
        array[i] = temp;

        quickSort(0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort(int begin, int end) {
        if (begin >= end) return;
        int index = partition(begin, end);
        quickSort(begin, index - 1);
        quickSort(index + 1, end);
    }

    private static int partition(int begin, int end) {
        int pivot = array[end];
        int j = begin - 1;
        for (int i = begin; i < end; i++) {
            if (array[i] < pivot) {
                j++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[end];
        array[end] = array[++j];
        array[j] = temp;
        return j;
    }
}
